public class Leetcode {
}
//leetcode:53:最大子数组和
class Solution1 {
    public int maxSubArray(int[] nums) {
        int n = nums.length;

        int[] dp = new int[n+1];
        int ret = Integer.MIN_VALUE;

        for(int i = 1; i <= n; i++){
            dp[i] = Math.max(nums[i-1] , dp[i-1] + nums[i-1]);
            ret = Math.max(ret , dp[i]);
        }
        return ret;
    }
}

//leetcode:918:环形子数组的最大和
class Solution2 {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;

        //设立两个数组f存入到i位置的最大值，g存入到i位置的最小值
        int[] f = new int[n+1];
        int[] g = new int[n+1];

        int ret1 = Integer.MIN_VALUE;
        int ret2 = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            f[i] = Math.max(nums[i-1] , f[i-1] + nums[i-1]);
            ret1 = Math.max(ret1 , f[i]);
            g[i] = Math.min(nums[i-1] , g[i-1] + nums[i-1]);
            ret2 = Math.min(ret2 , g[i]);
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += nums[i];
        }

        //如果此时我们整个数组的和为最小值，那么就返回整个数组的最大值即可，如果不等就返回整个数组的和减去最小值
        return sum == ret2 ? ret1 : Math.max(ret1 , sum - ret2);
    }
}